package com.example.rwq_test.niuke.tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 查找二叉树从根节点到某一节点的链路
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/20
 */
public class BinaryTreeLinkedNodeList {

    public static Deque<TreeNode> getBinaryTreeLinkedNodeList(TreeNode root, int v) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        if (root.val == v) {
            deque.offerFirst(root);
        } else {
            getBinaryTreeLinkedNodeList(root, v, deque);
            if (!deque.isEmpty()) {
                deque.offerFirst(root);
            }
        }
        return deque;
    }
    public static TreeNode getBinaryTreeLinkedNodeList(TreeNode root, int v, Deque<TreeNode> deque) {
        if (root == null || root.val == v) {
            return root;
        }
        TreeNode leftNode = getBinaryTreeLinkedNodeList(root.left, v, deque);
        if (leftNode != null) {
            deque.offerFirst(leftNode);
            return root;
        }
        TreeNode rightNode = getBinaryTreeLinkedNodeList(root.right, v, deque);
        if (rightNode != null) {
            deque.offerFirst(rightNode);
            return root;
        }
        return null;
    }

    public static void main(String[] args) {
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode0 = new TreeNode(0);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode9 = new TreeNode(9);

        treeNode3.left = treeNode5;
        treeNode3.right = treeNode1;
        treeNode5.left = treeNode6;
        treeNode5.right = treeNode2;
        treeNode1.left = treeNode0;
        treeNode1.right = treeNode8;
        treeNode2.left = treeNode7;
        treeNode2.right = treeNode4;
        treeNode7.right = treeNode9;
        Deque<TreeNode> arrayDeque = getBinaryTreeLinkedNodeList(treeNode3, 9);
        while (!arrayDeque.isEmpty()) {
            System.out.println(arrayDeque.pollFirst().val);
        }
        System.out.println("<=========================================>");
        getBinaryTreeLinkedNodeList1(treeNode3, 9);
        if (!queue.isEmpty()) {
            queue.offer(treeNode3);
        }
        while (!queue.isEmpty()) {
            System.out.println(queue.poll().val);
        }
    }

    private static final Queue<TreeNode> queue = new LinkedList<>();

    public static TreeNode getBinaryTreeLinkedNodeList1(TreeNode root, int v) {
        if (root == null || root.val == v) {
            return root;
        }
        TreeNode left = getBinaryTreeLinkedNodeList1(root.left, v);
        if (left != null) {
            queue.offer(left);
            return root;
        }
        TreeNode right = getBinaryTreeLinkedNodeList1(root.right, v);
        if (right != null) {
            queue.offer(right);
            return root;
        }
        return null;
    }
}
